Field of the Invention
This invention relates to a method of reducing the amount of data storage required to store a set of multi-dimensional coordinates and a method to recover the coordinate positions from the reduced data and, more particularly, to a method of reducing the data storage requirements of a terrain referenced navigation system while also providing an aliasing error reduction method.
Background of Terrain Referenced Navigation
One prior art terrain aided navigation system is available from Sandia Labs. Sandia has created the Sandia Inertial Terrain-Aided Navigation (SITAN) flight-computer algorithm that produces a very accurate trajectory for low-flying, high-performance aircraft by combining outputs from a radar or laser altimeter, an inertial navigation system (INS), and a digital terrain elevation map. SITAN is a recursive, real time, terrain-aided navigation algorithm for use on fighter aircraft. The algorithm has been implemented in a popular microprocessor. The aircraft's position can be estimated within a 926 meter circle error of probability. A good description of the SITAN terrain aided navigation system can be found in the proceedings of the IEEE National Aerospace and Electronics Conference--NAECON, May 20-24, 1985 entitled The AFTI/F16 Terrain-Aided Navigation System, by D. D. Boozer, M. K. Lau, J. R. Fellerhoff, Sandia National Laboratories, Albuquerque, N.M. 87185.
SITAN utilizes Kalman filter algorithms to process geophysical measurements. The algorithm estimates errors in a flight path produced by an inertial navigation system following the equations given in the above-mentioned article.
The Kalman filter can be formed with the following state model: EQU .delta.X.sub.k+1 =.phi..delta.X.sub.k +W.sub.k
and the measurement ##EQU1## where .delta.X.sub.k =INS error states to be estimated
.PHI.=slate-transition matrix for INS errors PA0 X.sub.k =states of INS and aircraft PA0 C.sub.k =ground clearance measurement PA0 Z.sub.k =altitude of aircraft PA0 h=height of terrain at position ( . , . ) PA0 W.sub.k =driving noise with E(W.sub.k)=O for all k and E(W.sub.k W.sub.j.sup.T)=Q.sub.k .delta..sub.kj PA0 V.sub.k =measurement error with E(V.sub.k)=O for all k and E(V.sub.k V.sub.j)=R.sub.k .delta..sub.kj PA0 k=Subscript denoting time k.
Since the measurement function c(x) is a nonlinear function of the states, the standard extended Kalman filter approach is used to obtain the measurement matrix, ##EQU2## where h.sub.x and h.sub.y are the terrain slopes in the x and y directions of the map evaluated at X.sub.k (-), the predicted aircraft position just before a measurement is processed at time k. The first three states are taken to be the x position, y position, and altitude, respectively. At any time k, EQU X=X.sub.INS +.delta.X
The state vector often used in a single filter implementation is EQU .delta.X=[.delta.X.delta.Y.delta.Z.delta.V.sub.X .delta.V.sub.Y ].sup.T
where .delta.X .delta.Y .delta.Z .delta.V.sub.X, and .delta.V.sub.Y are errors in the X position, Y position, altitude, X velocity, and Y velocity, respectively. Other INS errors and states can also be included in .delta.X by using the proper .PHI..
Parallel SITAN was developed because the distance needed by SITAN to reach steady state becomes excessive as initial position errors (IPEs) approach several hundred meters. Parallel SITAN is a bank of extended Kalman filters that process identical altimeter measurements. After some updates, the filter with the minimum average weighted residual squared (AWRS) value is identified as having the correct position estimate. The AWRS value is defined by ##EQU3## where .DELTA..sub.i is the residual at the ith update, n is the number of updates, and HPH.sup.T +R is the residual variance. Once the IPEs are reduced by the parallel filters, a single filter performs well, starting off essentially in steady state.
To implement parallel SITAN, the number and geometrical layout of the parallel filters needed to cover an IPE must be specified. A square, constant-spaced grid can be used to center the filters about the horizontal position indicated by the INS. Filters at and near the corners are then eliminated to reduce the number of filters. To further lighten the computational burden, three-state, instead of five-state, filters are often used in parallel SITAN with EQU .delta.X=[.delta.X.delta.Y.delta.X].sup.T
For both the single and parallel filter implementation, a least-squares plane fit to the map, known as stochastic linearization, is used to compute the slopes, h.sub.X and H.sub.Y. Horizontal uncertainties .sigma..sub.x and .sigma..sub.Y from the error-covariance matrix, defined by ##EQU4## and are used to determine the size of the plane. Residuals from the plane fit, RFIT.sub.k, are added to the measurement error variance, R.sub.k, to ensure that the SITAN filter assigns less weight to the measurement when the plane fit is either very large or is over a rough area, thus adapting to local terrain.
SITAN has three basic modes: acquisition mode, lost mode and track mode.
Acquisition Mode
When one of the filters identifies a reliable estimate of true aircraft position, the track mode is entered. A single five state Kalman filter is initialized at the estimated acquired position. During track mode, the aircraft's position is estimated every 100 meters. SITAN employs a mode control logic concept to handle the transition from track to lost and from acquisition to track.
Acquisition mode is used to locate the aircraft's position within a circular region of uncertainty. The region of uncertainty is called the circular error of probability or CEP. In SITAN a 2100 meter initial position CEP is covered with 57 3-state Kalman filters centered on a grid whose initial positions are 525 meters apart.
The state acquisition filters include error states. They can estimate an aircraft's position under significant INS velocity errors. Each filter is initialized with position error estimates. To ensure that erroneous information is not employed to update the filters, none of the filters are updated if the pitch altitude is greater than 30 degrees or if the altimeter loses lock or the INS fails.
If the mode control logic of SITAN indicates that the aircraft has deviated from the 2363 meter search area, the lost mode is initiated. The lost mode ceases to provide position estimates for the aircraft, and the pilot has to update the inertial navigation before restarting SITAN.
Track Mode
Track mode estimates the position of the aircraft during flight. The five state tracking filter is used. The acquisition mode initializes the track filters. The track mode makes estimates of terrain slopes in rectangles surrounding the center of the aircraft position. The track filters are not updated during track mode unless the inertial navigation system, altimeter, and other flight data are valid.
Track mode is entered when the aircraft's actual position is close to the estimated one. In the event of a false fix, the track filter is set at the wrong position and the SITAN algorithm will proceed as if it was correct. This produces large errors in estimated positions. It is imperative that the probability of a false fix be kept low. The following is taken from the above-mentioned article in regard to the mode control logic of SITAN.
With the design for the acquisition, lost, and track modes as described above, the mode-control logic is needed to determine in which mode the algorithm should operate. When large aircraft position errors exist, it should choose the acquisition mode; with small errors, the track. The main parameter used in the mode-control logic for transition from acquisition to track is the AWRS. FIG. 7 shows a cross-section of a three-dimensional AWRS surface where AWRS is a function of the parallel filter positions (X.sub.j, Y.sub.j). In the acquisition mode the parallel filters will tend to migrate to the relative minima of this surface.
To keep the parallel filters from migrating too far from their initial positions, a maximum of 128 updates is allowed. Four tests are performed after every 32 updates to determine if transition to the track mode is possible by selecting the acquisition filter with the minimum AWRS. Test 1 requires the selected filter to have an AWRS lower than a threshold value to ensure that the parallel filters are indeed over the correct aircraft position. If the parallel filters are configured over an area which does not include the true aircraft position, the global minimum of the AWRS curve is expected to shift upward. Test 2 requires contrast in the terrain, a sufficient difference between AWRS.sub.min and AWRS.sub.max to prevent transition to the track mode over very smooth areas such as water. Test 3, the false-fix test, requires that the minimum AWRS outside of an exclusion region, AWRS*.sub.min does not compete with AWRS.sub.min, where the size of the exclusive region is computed using .sigma..sub.x and .sigma..sub.Y of the selected filter. Statistically, as more updates are made, the separation between the global minimum and relative minima can be realized and still retain the same confidence level. Therefore, the required separation between AWRS*.sub.min and AWRS.sub.min should be a function of l/n, where n is the number of updates. Test 4 requires the .sigma..sub.X and .sigma..sub.Y of the selected filter to be smaller than its initial value, 200 m, indicating that improvements have been made in estimating the aircraft's position during acquisition.
If track is not entered after 128 updates, a test for the lost mode is made. If AWRS.sub.min is greater than a threshold, the lost mode is entered and AFTI/SITAN will not produce any more estimates until the pilot updates the INS, which will automatically restart AFTI/SITAN in the track mode. If the lost condition is not met, the parallel filters are reset and acquisition starts over. This process continues until track or lost mode is entered.
Once in track, the track filter's .sigma..sub.x and .sigma..sub.Y are checked continuously while its AWRS is checked every 64 updates. If either the .sigma.'s or the AWRS is too high, AFTI/SITAN switches back to the acquisition mode. The test on .sigma. prevents the track filter from using excessively large plane fits to maintain track after flying over smooth terrain for a long time. The AWRS test checks for unbelievable filter residuals.
Discussion of the Prior Art
Data storage requirements in real time computer applications require voluminous amounts of information to be stored both in RAM and on permanent storage devices such as a disk or tape. Most real time applications of data storage require some sort of a mapping of a real environment or a set of parameters. In the area of mapping and navigation, the problem of characterizing the environment in a multi-dimensional database is even more complicated and more complex. The types of information stored in such real time, real world applications range from the physical to the topological characteristics of the location.
A good example of a real time application that is characterized by large data storage requirements is a terrain referenced navigation system in which each physical feature of a terrain area is mapped into memory. This representation of the terrain resides on a permanent storage medium such as a magnetic disk, tape, or optical disk and is referenced in the usual fashion of latitude and longitude. In the case of a terrain referenced navigation system, the elevation of each latitude and longitude sampled point is stored. For instance, if an area is to be represented in a latitude/longitude elevation survey, it would require, for each latitude/longitude point, a certain number of bits equal to the resolution of the height being resolved. For example, if 256 discrete elevations are to be resolved, then 8 bits of data need to be dedicated to each latitude/longitude point. In another example, if 65,000 elevations are to be resolved then 16 bits of data need to be assigned to every latitude/longitude point. In yet another example, a 1,000.times.1,000 latitude/longitude grid storing 16 points of data for each elevation would require 16 million bits of data storage.
The prior art method of reducing data storage requirements for terrain referenced navigation real time applications utilized the discrete cosine transform/differential pulse code modulation method. While this method achieves very high compression ratios, it also introduces relatively large data errors when compared to the method described herein. Traditional methods of data compression and decompression require that the information no longer be viewed as a latitude/longitude elevation study, but in fact be viewed as a set of sequential serial bit streams which are compressed using various schemes well known in the prior art. Sequential bit stream compression algorithms cannot be used in flight trajectory algorithms. Since elevation data must be available for any given flight path, the elevation data must be directly accessible for any randomly chosen latitude/longitude the aircraft happens to overfly. This drawback of the prior art, along with the advantages of using data compression and decompression are important motivations for the invention.
Prior art data compression and decompression algorithms have also suffered from aliasing error. Aliasing error is the error induced when real world analog information is quantized in a digital fashion. A good example of this is the quantization of altitude data wherein the altitude ranges from 0 feet above sea level to 1,000 feet above sea level where 100 samples will be taken. The accuracy of any sample relative to other samples will be 10 feet. There are 100.times.10 samples being taken. In this example, the aliasing error would be five feet because such sampling provides an accurate representation of the altitude within five feet. As a more specific example, if a sample point is taken at 910 feet, this technique assures that the data point value ranges between 910-5 and 910+5 feet. Thus, the aliasing error of the sampling technique, or the storage technique that is required when any analog real time system is being converted to a digital processing system, is the fundamental limitation on accuracy inherent in any scheme whether it is data compression or just data storage.